\documentclass[twoside,a4paper]{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{NAME Jiatu Yan}
\chead{Numerical PDE/ODE Project02 - math}
\rhead{Date 2021.6.9}


\section*{I. Problem}
The problem we want to solve with multigrid methods is the Poisson equation, which is
\[
\left\{
	\begin{array}{l}
		-\bigtriangleup u\left( x \right)  = f\left( x \right) \quad x\in \Omega := \left( 0, 1 \right)^{\dim},\\
		u\left( x \right)  = g\left( x \right) \quad x\in\partial\Omega.
	\end{array}
	\right.
\] 
We can discretize the problem into a uniform grid. For the given cell size $h = \frac{1}{N}$, we can set the coordinate of each knots.
For example, in the space $\left[ 0, 1 \right]^{\dim} $, we denot 
$x=\left\{k_1, k_2, \ldots, k_{\dim}  \right\}=\left( hk_1, hk_2,\ldots,hk_{\dim} \right)  $.
We denot all the knots on the grid as set $G$ and the set containing the boundary of the grid as $\partial G$.
Obviously, we can define the addition about this coordinate.
Assume $e_i = \{a_1, \ldots, a_{\dim}\}$, where $a_j=0$ for $j\neq i$ and $a_i=1$.
Thus we can write out the Lapace operator in the grid, which is
\[
	f\left( x \right)=\frac{1}{h^2}\left(\dim \cdot u\left( x \right)-
	\sum_{i=0}^{\dim}\left[u\left( x+e_i \right)-u\left( x-e_i \right)\right]    \right)   
	\quad x\in\partial G
.\] 

We can find that the discretized Lapace operator is linear, which means we can write it into matrix form.
We denote $\tilde{A}$, whose size is $\left( N+1 \right)^{\dim}  $, as the Lapace operator.
For a coordinate $x$,  $a_x=0$ if we can not find $e_i$ such that $x+e_i\in G \setminus \partial G$
To solve the Possion equation, we need to solve the linear equations $\tilde A u=F$.
From the Dirichlet boundary condition, we have known the true value of u on the boundary.
Then we can move those known $u$ to the right of the equation.
Now we achieved a linear equations $Au=\tilde F$, where A is the one discussed in Chapter 9.

The model problem we want to solve by multigrid methods is the one-dimensional Possion problem with homogeneous condition.

\section*{II. Fourier modes}

As we only discuss the homogeneous boundary condition, we can odd expand the function on $\left[0, 1\right]$ to  $\mathbb{R}$.
Then the fourier expansion of the function only contains the elements about sine function.
While the number of sine functions that can be represented on the grid is finite.
But the smoother the function is, the residual about the sine functions which cannot be represented in the grid
is smaller, for their wave number is large.

Thus for the given initial guess of u, we want to minimize the error induced by the fourier modes with smaller wave number,
which dominate the total error.

\section*{III. Classical iterative method}

To solve the function $Au=f$, we can use weighted Jacobi method. From the figure we get in Exercise 9.28, we know that
the Jacobi method can damp the error induced by high-frequency modes very quickly.
But the error induced on low-grequency modes will be dampped slowly. 
In other words, the total error will go down very slowly. 

Then we need to modify the iterative method which can eliminate the error on low-frequency modes.

\section*{IV. Multigrid cycles}

For the sake of convenience, we denote the grid with grid size h as $g_h$.
For V-cycle, we smooth the equation by weighted Jacobi method for several times and get $\tilde{u}$. 
The error on high-frequency modes is damped quickly.
Then we get the error $e=u^{*}-\tilde{u}$ and residual $r=f-A\tilde{u}$.
We have
\[
	Ae=A\left( u^{*}-\tilde{u} \right)=r 
.\] 
Now we reduce the function into the rsidual equation. 

e is constructed by the low-frequency modes in the present grid $g_h$.
To eliminate the error, we can restrict it into the coareser grid $g_{2h}$ and, as shown in Lemma 9.29,
half of the LF modes in $g_h$ becomes HF in the coareser grid $g_{2h}$.
We can easily eliminate it by smoothing it.

Then we can deduce the residual function and restrict it to a coarser grid $g_{4h}$ again.
Half of the LF modes in $g_2h$ becomes HF modes in $g_{4h}$ and we can annihilate the error induced by them in $g_{4h}$. 

Do this for several times and we will step into a very coarse grid. The grid is so coarse that it only contains about 9 knots or less. We can calculate the solution of the residual equation precisely on this grid and eliminate the error on LF modes.

Now we interpolate the residual back to the finer grid and smooth again to eliminate the error on HF modes induced by interpolation operator.
Do this for several times until we go back to the finest grid. We put the modified residual back to $\tilde{u}$ and smooth it.

Now we go through one V-cycle, the error induced by LF  modes is annihilated quickly when we go through the coarse grids and
the one induced by HF modes is eliminated by weighted Jacobi method. Thus we can get good convergence rate of the iteration.

\section*{V. Full multigrid V-cycle}

For the full multigrid V-cycle, we restrict the right side of the equation to the coarest grid.
As we know the equation, we can also set the right side with precise value of $f$ rather than restrict it from finer grids.

In the coarest grid, we perform V-cycle for one or more times and interpolate the solution back to finer grid.
Now we get a precise initial guess for the V-cycle starting at the present grid.
Do this for several times and we go back to the finest grid.

We know that all the V-cycle is performed with a precise initial guess and V-cycle can reduce the error efficiently.
Thus we can get a good solution on the finest grid with small error on both LF and HF modes.
The more V-cycles we do in each grid, the more precise the initial guess we get for the next V-cycle and we will 
get the more presice solution.

\section*{VI. Nonhomogeneous boundary condition}
For the case in which the dimension is one, we can easily seperate the boundary conditions out as discussed in
Theorem 8.42. Thus we can change all the nonhomogeneous problems into homogeneous one.

If we move the boundary value to the right side of the equation as what we have done in section I, we may deduce a 
residual function in II. 
But I think this may induce an error in the high Fourier modes which even cannot be represented on the grid. 
As when we cut out the boundary values, the function $\tilde{F}$ on the right sides actually becomes a uncontinuous function, in which exists a sharp perturbation on the knots next to the boundary.

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
